Search Results

Documents authored by Kundu, Madhumita

Document
DOI: 10.4230/LIPIcs.ITCS.2024.64
Exponential-Time Approximation Schemes via Compression

Authors: Tanmay Inamdar, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
In this paper, we give a framework to design exponential-time approximation schemes for basic graph partitioning problems such as k-way cut, Multiway Cut, Steiner k-cut and Multicut, where the goal is to minimize the number of edges going across the parts. Our motivation to focus on approximation schemes for these problems comes from the fact that while it is possible to solve them exactly in 2^nn^{{𝒪}(1)} time (note that this is already faster than brute-forcing over all partitions or edge sets), it is not known whether one can do better. Using our framework, we design the first (1+ε)-approximation algorithms for the above problems that run in time 2^{f(ε)n} (for f(ε) < 1) for all these problems. As part of our framework, we present two compression procedures. The first of these is a "lossless" procedure, which is inspired by the seminal randomized contraction algorithm for Global Min-cut of Karger [SODA '93]. Here, we reduce the graph to an equivalent instance where the total number of edges is linearly bounded in the number of edges in an optimal solution of the original instance. Following this, we show how a careful combination of greedy choices and the best exact algorithm for the respective problems can exploit this structure and lead to our approximation schemes. Our first compression procedure bounds the number of edges linearly in the optimal solution, but this could still leave a dense graph as the solution size could be superlinear in the number of vertices. However, for several problems, it is known that they admit significantly faster algorithms on instances where solution size is linear in the number of vertices, in contrast to general instances. Hence, a natural question arises here. Could one reduce the solution size to linear in the number of vertices, at least in the case where we are willing to settle for a near-optimal solution, so that the aforementioned faster algorithms could be exploited? In the second compression procedure, using cut sparsifiers (this time, inspired by Benczúr and Karger [STOC '96]) we introduce "solution linearization" as a methodology to give an approximation-preserving reduction to the regime where solution size is linear in the number of vertices for certain cut problems. Using this, we obtain the first polynomial-space approximation schemes faster than 2^nn^{{𝒪}(1)} for Minimum bisection and Edge Bipartization. Along the way, we also design the first polynomial-space exact algorithms for these problems that run in time faster than 2^nn^{{𝒪}(1)}, in the regime where solution size is linear in the number of vertices. The use of randomized contraction and cut sparsifiers in the exponential-time setting is novel to the best of our knowledge and forms our conceptual contribution.
Cite as

Tanmay Inamdar, Madhumita Kundu, Pekka Parviainen, M. S. Ramanujan, and Saket Saurabh. Exponential-Time Approximation Schemes via Compression. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 64:1-64:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{inamdar_et_al:LIPIcs.ITCS.2024.64,
  author =	{Inamdar, Tanmay and Kundu, Madhumita and Parviainen, Pekka and Ramanujan, M. S. and Saurabh, Saket},
  title =	{{Exponential-Time Approximation Schemes via Compression}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{64:1--64:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.64},
  URN =		{urn:nbn:de:0030-drops-195920},
  doi =		{10.4230/LIPIcs.ITCS.2024.64},
  annote =	{Keywords: Exponential-Time Algorithms, Approximation Algorithms, Graph Algorithms, Cut Problems}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2023.28
FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less

Authors: Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, M. S. Ramanujan, and Saket Saurabh

Published in: LIPIcs, Volume 284, 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)

Abstract
For numerous graph problems in the realm of parameterized algorithms, using the size of a smallest deletion set (called a modulator) into well-understood graph families as parameterization has led to a long and successful line of research. Recently, however, there has been an extensive study of structural parameters that are potentially much smaller than the modulator size. In particular, recent papers [Jansen et al. STOC 2021; Agrawal et al. SODA 2022] have studied parameterization by the size of the modulator to a graph family ℋ(mod_ℋ(⋅)), elimination distance to ℋ(ed_ℋ(⋅)), and ℋ-treewidth (tw_ℋ(⋅)). These parameters are related by the fact that tw_ℋ lower bounds ed_ℋ, which in turn lower bounds mod_ℋ. While these new parameters have been successfully exploited to design fast exact algorithms their utility (especially that of ed_ℋ and tw_ℋ) in the context of approximation algorithms is mostly unexplored. The conceptual contribution of this paper is to present novel algorithmic meta-theorems that expand the impact of these structural parameters to the area of FPT Approximation, mirroring their utility in the design of exact FPT algorithms. Precisely, we show that if a covering or packing problem is definable in Monadic Second Order Logic and has a property called Finite Integer Index (FII), then the existence of an FPT Approximation Scheme (FPT-AS, i.e., (1±ε)-approximation) parameterized by mod_ℋ(⋅), ed_ℋ(⋅), and tw_ℋ(⋅) is in fact equivalent. As a consequence, we obtain FPT-ASes for a wide range of covering, packing, and domination problems on graphs with respect to these parameters. In the process, we show that several graph problems, that are W[1]-hard parameterized by mod_ℋ, admit FPT-ASes not only when parameterized by mod_ℋ, but even when parameterized by the potentially much smaller parameter tw_ℋ(⋅). In the spirit of [Agrawal et al. SODA 2022], our algorithmic results highlight a broader connection between these parameters in the world of approximation. As concrete exemplifications of our meta-theorems, we obtain FPT-ASes for well-studied graph problems such as Vertex Cover, Feedback Vertex Set, Cycle Packing and Dominating Set, parameterized by tw_ℋ(⋅) (and hence, also by mod_ℋ(⋅) or ed_ℋ(⋅)), where ℋ is any family of minor free graphs.
Cite as

Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, M. S. Ramanujan, and Saket Saurabh. FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less. In 43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 284, pp. 28:1-28:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{inamdar_et_al:LIPIcs.FSTTCS.2023.28,
  author =	{Inamdar, Tanmay and Kanesh, Lawqueen and Kundu, Madhumita and Ramanujan, M. S. and Saurabh, Saket},
  title =	{{FPT Approximations for Packing and Covering Problems Parameterized by Elimination Distance and Even Less}},
  booktitle =	{43rd IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2023)},
  pages =	{28:1--28:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-304-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{284},
  editor =	{Bouyer, Patricia and Srinivasan, Srikanth},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2023.28},
  URN =		{urn:nbn:de:0030-drops-194013},
  doi =		{10.4230/LIPIcs.FSTTCS.2023.28},
  annote =	{Keywords: FPT-AS, F-Deletion, Packing, Elimination Distance, Elimination Treewidth}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2023.55
Fixed-Parameter Algorithms for Fair Hitting Set Problems

Authors: Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Nidhi Purohit, and Saket Saurabh

Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)

Abstract
Selection of a group of representatives satisfying certain fairness constraints, is a commonly occurring scenario. Motivated by this, we initiate a systematic algorithmic study of a fair version of Hitting Set. In the classical Hitting Set problem, the input is a universe 𝒰, a family ℱ of subsets of 𝒰, and a non-negative integer k. The goal is to determine whether there exists a subset S ⊆ 𝒰 of size k that hits (i.e., intersects) every set in ℱ. Inspired by several recent works, we formulate a fair version of this problem, as follows. The input additionally contains a family ℬ of subsets of 𝒰, where each subset in ℬ can be thought of as the group of elements of the same type. We want to find a set S ⊆ 𝒰 of size k that (i) hits all sets of ℱ, and (ii) does not contain too many elements of each type. We call this problem Fair Hitting Set, and chart out its tractability boundary from both classical as well as multivariate perspective. Our results use a multitude of techniques from parameterized complexity including classical to advanced tools, such as, methods of representative sets for matroids, FO model checking, and a generalization of best known kernels for Hitting Set.
Cite as

Tanmay Inamdar, Lawqueen Kanesh, Madhumita Kundu, Nidhi Purohit, and Saket Saurabh. Fixed-Parameter Algorithms for Fair Hitting Set Problems. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 55:1-55:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{inamdar_et_al:LIPIcs.MFCS.2023.55,
  author =	{Inamdar, Tanmay and Kanesh, Lawqueen and Kundu, Madhumita and Purohit, Nidhi and Saurabh, Saket},
  title =	{{Fixed-Parameter Algorithms for Fair Hitting Set Problems}},
  booktitle =	{48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)},
  pages =	{55:1--55:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-292-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{272},
  editor =	{Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.55},
  URN =		{urn:nbn:de:0030-drops-185897},
  doi =		{10.4230/LIPIcs.MFCS.2023.55},
  annote =	{Keywords: Fairness, Parameterized Algorithms, Hitting Set}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact